A graph is a data structure commonly used to present data in a structured manner. A graph consists of nodes and links where each node represents an object and a link, also known as an “edge”, connects a source node to a target node. Graphs are commonly used in a variety of applications to model the flow of information, to model the relationship between entities, and so forth. For example, in a social network, the nodes of the graph may represent individuals and the edges may represent a relationship between two individuals. In an airline network, the nodes may represent cities and a sequence of edges may represent routes from one city to another.
A node-link diagram is a construct used to visualize a graph where a graphical object, such as a box or dot, depicts a node and a curve is used to represent a link between two nodes. A node-link diagram having a large number of nodes and links suffers from visual clutter. The visual clutter is often attributable to link congestion when multiple links overlap each other making it difficult to distinguish a particular link or a subset of links.